1734C - Removing Smallest Multiples - CodeForces Solution

import os
import sys
import math
from collections import deque, defaultdict
from bisect import bisect_left, bisect_right
import heapq
import itertools

input = sys.stdin.readline


def multiple():
    a = map(int, input().split())
    return a


def array():
    a = input().split()
    return a


def intarray():
    a = list(map(int, input().split()))
    return a


def intinput():
    n = int(input())
    return n


def strinput():
    s = input().strip()
    return s


def isPrime(n):
    val = int(math.sqrt(n)) + 1
    for i in range(2, val):
        if n % i == 0:
            return False
    return True


def power(x, y, p):
    res = 1
    x = x % p

    if (x == 0):
        return 0

    while (y > 0):
        if ((y & 1) == 1):
            res = (res * x) % p

        y = y >> 1
        x = (x * x) % p

    return res


def modexp(x, n, m):
    if (n == 0):
        return 1

    elif (n % 2 == 0):
        return modexp((x * x) % m, n // 2, m)

    else:
        return (x * modexp((x * x) % m,
                           (n - 1) / 2, m) % m)


def getFractionModulo(a, b, m):
    c = math.gcd(a, b)

    a = a // c
    b = b // c

    d = modexp(b, m - 2, m)

    ans = ((a % m) * (d % m)) % m

    return ans


def factorial(n, dp):
    if dp[n] != 0:
        return dp[n]
    val = 1
    for i in range(2, n + 1):
        val *= i
        dp[i] = val
    return val


def notmultiple(a, b):
    while a % b == 0:
        a = a // b
    if a == 1:
        return False
    return True

def median(a):
    n = len(a)
    if n%2 == 0:
        val1 = n//2
        val2 = val1-1
        return (a[val1] + a[val2])/2
    else:
        val1 = n//2
        return a[val1]

def solution():
            n = intinput()
    s = strinput()
    a = [0]*(n+1)
    for i in range(1,n+1):
        if s[i-1] == '1':
            a[i] = 1
    ans = 0
    cost = [0]*(n+1)
    for i in range(n,0,-1):
        for j in range(i,n+1,i):
            if a[j] == 1:
                break
            cost[j] = i
    for i in range(1,n+1):
        if a[i] != 1:
            ans += cost[i]
    print(ans)
    return

t = 1
t = int(input())
for _ in range(t):
            solution()